﻿//Write a program that reads three integer numbers N, K and S and an array of N elements from the console.
//Find in the array a subset of K elements that have sum S or indicate about its absence.



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _17SubsetSum2._0
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Array size (N):");
            string strArraySize = Console.ReadLine();
            int arraySize = int.Parse(strArraySize);
            int[] array = new int[arraySize];
            for (int i = 0; i <= array.Length - 1; i++)
            {
                Console.Write("array[{0}]:", i);
                string strElement = Console.ReadLine();
                array[i] = int.Parse(strElement);
            }
            Console.WriteLine("The array looks like this:");
            foreach (var item in array)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
            Console.Write("What sum are we looking for (S):");
            string strS = Console.ReadLine();
            int s = int.Parse(strS);
            Console.Write("How many elements should form this sum (K):");
            string strK = Console.ReadLine();
            int k = int.Parse(strK);
            Console.WriteLine("-------------------------------------------------------");
            int maxSubSets = (int)Math.Pow(2, array.Length);
            int checkSum = 0;
            int subsetLength = 0;
            int foundAny = 0;
            string elements = "";
            for (int i = 1; i < maxSubSets; i++)
            {
                elements = "";
                checkSum = 0;
                subsetLength = 0;
                for (int j = 0; j <= array.Length; j++)
                {
                    int mask = 1 << j;
                    int andMask = i & mask;
                    int bit = andMask >> j;
                    if (bit == 1)
                    {
                        checkSum += array[j];
                        elements += " " + array[j];
                        subsetLength++;
                    }
                }
                if ((checkSum == s) && (k == subsetLength))
                {
                    Console.WriteLine("S={0} Yes: ({1})", s, elements);
                    foundAny++;
                }
            }
            if (foundAny == 0)
            {
                Console.WriteLine("No such animal!");
            }
        }
    }
}
